#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <vector>
#include <utility>
#include <set>

using namespace std;

struct rect
{
	int h,w;
};

struct space
{
	int x,y,h,w;
	space(int x1, int y1, int w1, int h1)
	{
		x=x1;
		y=y1;
		w=w1;
		h=h1;
	}
	space();
};

double genrand()
{
	return (double)rand()/(double)(RAND_MAX);
}

// Inputs
int h,w,n,tot_area;
rect *rects;

// GA population
int **pop, **orient;

int blf(int pos, bool output=false)
{
	int i,j,rectw,recth,x,y,minx,miny;

	vector <space> empty;	// Stores the filled spaces
	for (i=0;i<n;i++)
	{
		if (orient[pos][i]==0)
		{
			rectw = rects[pop[pos][i]].w;
			recth = rects[pop[pos][i]].h;
		}
		else
		{
			rectw = rects[pop[pos][i]].h;
			recth = rects[pop[pos][i]].w;
		}

		bool flag = true;
		// Find bottom left coordinate
		for (y=0;y<=h-recth;y++)
		{
			miny = h;
			for (x=0;x<=w-rectw;x++)
			{
				// Check if it is overlapping
				flag = true;
				minx = w;
				for (j=0;j<empty.size();j++)
				{
					if (x < empty[j].x + empty[j].w &&
						x + rectw >= empty[j].x &&
						y < empty[j].y + empty[j].h &&
						y + recth >= empty[j].y)
					{
						flag = false;
						//x = empty[j].x + empty[j].w - 1;
						if (empty[j].x + empty[j].w - 1 < minx)
							minx = empty[j].x + empty[j].w - 1;
						if (empty[j].y + empty[j].h - 1 < miny)
							miny = empty[j].y + empty[j].h - 1;
					}
				}

				if (flag)
				{
					if (output)
						cout << "<rect name=\"" << i << "\" x1=\"" <<
							x << "\" y1=\"" << y << "\" x2=\"" << x+rectw << "\" y2=\""<<y+recth<<"\"/>"<<endl;
					space s(x,y,rectw,recth);
					empty.push_back(s);
					break;
				}
				else
					x = minx;
			}
			if (flag)
				break;
			else
				y = miny;
		}
	}

	j=0;
	for (i=0;i<empty.size();i++)
	{
		j += empty[i].w * empty[i].h;
	}
	return j;
}

int fc(int pos, bool output=false)
{
	int i,j,rectw,recth,x,y,minx,miny;
	int corner=0;

	vector <space> empty;	// Stores the filled spaces
	for (i=0;i<n;i++)
	{
		if (orient[pos][i]==0)
		{
			rectw = rects[pop[pos][i]].w;
			recth = rects[pop[pos][i]].h;
		}
		else
		{
			rectw = rects[pop[pos][i]].h;
			recth = rects[pop[pos][i]].w;
		}

		bool flag = true;

		switch (corner)
		{
		case 0:	// Find bottom left coordinate
			for (y=0;y<=h-recth;y++)
			{
				miny = h;
				for (x=0;x<=w-rectw;x++)
				{
					// Check if it is overlapping
					flag = true;
					minx = w;
					for (j=0;j<empty.size();j++)
					{
						if (x < empty[j].x + empty[j].w &&
							x + rectw > empty[j].x &&
							y < empty[j].y + empty[j].h &&
							y + recth > empty[j].y)
						{
							flag = false;
							if (empty[j].x + empty[j].w - 1 < minx)
								minx = empty[j].x + empty[j].w - 1;
							if (empty[j].y + empty[j].h - 1 < miny)
								miny = empty[j].y + empty[j].h - 1;
						}
					}

					if (flag)
					{
						if (output)
							cout << "<rect name=\"" << i << "\" x1=\"" <<
								x << "\" y1=\"" << y << "\" x2=\"" << x+rectw << "\" y2=\""<<y+recth<<"\"/>"<<endl;
						space s(x,y,rectw,recth);
						empty.push_back(s);
						break;
					}
					else
						x = minx;
				}
				if (flag)
					break;
				else
					y = miny;
			}
			break;
		case 1: // Find top right coordinate
			for (y=h-recth;y>=0;y--)
			{
				miny = 0;
				for (x=w-rectw;x>=0;x--)
				{
					// Check if it is overlapping
					flag = true;
					minx = 0;
					for (j=0;j<empty.size();j++)
					{
						if (x < empty[j].x + empty[j].w &&
							x + rectw > empty[j].x &&
							y < empty[j].y + empty[j].h &&
							y + recth > empty[j].y)
						{
							flag = false;
							if (empty[j].x - rectw + 1 > minx)
								minx = empty[j].x + 1 - rectw;
							if (empty[j].y - recth + 1 > miny)
								miny = empty[j].y + 1 - recth;
						}
					}

					if (flag)
					{
						if (output)
							cout << "<rect name=\"" << i << "\" x1=\"" <<
								x << "\" y1=\"" << y << "\" x2=\"" << x+rectw << "\" y2=\""<<y+recth<<"\"/>"<<endl;
						space s(x,y,rectw,recth);
						empty.push_back(s);
						break;
					}
					else
						x = minx;
				}
				if (flag)
					break;
				else
					y = miny;
			}
			break;
		case 2:
			// Find bottom right coordinate
			for (y=0;y<=h-recth;y++)
			{
				miny = h;
				for (x=w-rectw;x>=0;x--)
				{
					// Check if it is overlapping
					flag = true;
					minx = 0;
					for (j=0;j<empty.size();j++)
					{
						if (x < empty[j].x + empty[j].w &&
							x + rectw > empty[j].x &&
							y < empty[j].y + empty[j].h &&
							y + recth > empty[j].y)
						{
							flag = false;
							if (empty[j].x - rectw + 1 > minx)
								minx = empty[j].x + 1 - rectw;
							if (empty[j].y + empty[j].h - 1 < miny)
								miny = empty[j].y + empty[j].h - 1;
						}
					}

					if (flag)
					{
						if (output)
							cout << "<rect name=\"" << i << "\" x1=\"" <<
								x << "\" y1=\"" << y << "\" x2=\"" << x+rectw << "\" y2=\""<<y+recth<<"\"/>"<<endl;
						space s(x,y,rectw,recth);
						empty.push_back(s);
						break;
					}
					else
						x = minx;
				}
				if (flag)
					break;
				else
					y = miny;
			}
			break;
		case 3:
			// Find top left coordinate
			for (y=h-recth;y>=0;y--)
			{
				miny = 0;
				for (x=0;x<=w-rectw;x++)
				{
					// Check if it is overlapping
					flag = true;
					minx = w;
					for (j=0;j<empty.size();j++)
					{
						if (x < empty[j].x + empty[j].w &&
							x + rectw > empty[j].x &&
							y < empty[j].y + empty[j].h &&
							y + recth > empty[j].y)
						{
							flag = false;
							if (empty[j].x + empty[j].w - 1 < minx)
								minx = empty[j].x + empty[j].w - 1;
							if (empty[j].y - recth + 1 > miny)
								miny = empty[j].y + 1 - recth;
						}
					}

					if (flag)
					{
						if (output)
							cout << "<rect name=\"" << i << "\" x1=\"" <<
								x << "\" y1=\"" << y << "\" x2=\"" << x+rectw << "\" y2=\""<<y+recth<<"\"/>"<<endl;
						space s(x,y,rectw,recth);
						empty.push_back(s);
						break;
					}
					else
						x = minx;
				}
				if (flag)
					break;
				else
					y = miny;
			}
			break;
		}

		corner = (corner+1)%4;
	}

	j=0;
	for (i=0;i<empty.size();i++)
	{
		j += empty[i].w * empty[i].h;
	}
	return j-(n-empty.size())*tot_area/n;
}

int main()
{
	srand((unsigned)time(NULL));

	int i,j,k,p;
	tot_area=0;
	//cout << "Width: ";
	cin >> w;
	//cout << "Height: ";
	cin >> h;
	//cout << "No. of rectangles: ";
	cin >> n;

	rects = new rect[n];
	for (i=0;i<n;i++)
	{
		//cout << "Rectangle " << i+1 << ":";
		cin >> rects[i].w;
		cin >> rects[i].h;
		tot_area += rects[i].w*rects[i].h;
	}
	//****************************************

	// GA variables
	int popsize=50;
	int iterations=30;
	int tournament_size=2;
	int **mating, **matingorient, *rank;
	int *child1, *child2, *child1orient, *child2orient, temp;
	bool flag;
	double *fitness;
	double total_fitness, min, max=-5000, pos;
	double pc=0.6;
	double pmswap=0.01;
	double pmrotate=1.0/popsize;
	int site;

	pop = new int*[popsize];
	mating = new int*[popsize];
	orient = new int*[popsize];
	matingorient = new int*[popsize];
	fitness = new double[popsize];
	rank = new int[popsize];
	child1 = new int[n];
	child2 = new int[n];
	child1orient = new int[n];
	child2orient = new int[n];
	for (i=0;i<popsize;i++)
	{
		pop[i] = new int[n];
		mating[i] = new int[n];
		orient[i] = new int[n];
		matingorient[i] = new int[n];
		for (j=0;j<n;j++)
		{
			pop[i][j] = 0;
			mating[i][j] = 0;
			orient[i][j] = 0;
			matingorient[i][j] = 0;
		}
	}

	cout << "<?xml version=\"1.0\" encoding=\"UTF-8\"?><space x=\"" << w << "\" y=\"" << h << "\">"<<endl;

	// Generate random initial solutions
	for (i=0;i<popsize;i++)
	{
		for (j=0;j<n;j++)
		{
			pop[i][j] = j;
			orient[i][j] = 0;
		}
	}


	// Main GA loop
	for (p=0;p<iterations;p++)
	{
		// Find fitness of each individual
		total_fitness=0;
		for (i=0;i<popsize;i++)
		{
			fitness[i]=fc(i);
			if (fitness[i] > max)
			{
				max = fitness[i];
				pos = i;
			}
			total_fitness += fitness[i];
		}
		//cout << total_fitness/popsize << endl;

		// Find mating pool (selection)
		// Tournament selection
		for (i=0;i<popsize;i++)
		{
			// Initialize rank array
			for (j=0;j<popsize;j++)
				rank[j] = -1;

			// Select individuals for tournament
			for (j=0;j<tournament_size;j++)
			{
				temp = (int)(genrand() * (popsize-1));

				if (rank[temp] == -1)
				{
					rank[temp] = 1;
				}
				else
				{
					for (k=temp+1;k<popsize;k++)
					{
						if (rank[k] == -1)
						{
							rank[k] = 1;
							break;
						}
					}
					if (k==popsize)
						j--;
				}
			}

			// Perform tournament
			min = -1e20;
			for (j=0;j<popsize-1;j++)
			{
				if (rank[j] != -1 && fitness[j] > min)
				{
					min = fitness[j];
					temp = j;
				}
			}

			// Copy individuals to mating pool
			for (j=0;j<n;j++)
			{
				mating[i][j] = pop[temp][j];
				matingorient[i][j] = orient[temp][j];
			}
		}
		for (i=0;i<popsize;i++)
			rank[i]=-1;
		// Do pairing of solutions
		for (i=0;i<popsize;i++)
		{
			if (rank[i] != -1)
				continue;
			temp = (int)(genrand() * (popsize-1));
			if (temp == i)
			{
				i--;
				continue;
			}
			if (rank[temp] == -1)
			{
				rank[temp] = i;
				rank[i] = temp;
				continue;
			}
			for (j=temp;j<popsize;j++)
			{
				if (j == i)
					continue;
				if(rank[j] == -1)
					break;
			}
			if (j == popsize)
			{
				i--;
				continue;
			}
			rank[j] = i;
			rank[i] = j;
		}
		// Crossover
		for (i=0;i<popsize;i++)
		{
			if (rank[i] == -1)
				continue;
			if (genrand() < pc)
			{
				k = (int)(genrand()*(n-1));
				// Copy first half
				for (j=0;j<k;j++)
				{
					child1[j] = mating[i][j];
					child1orient[j] = matingorient[i][j];
					child2[j] = mating[rank[i]][j];
					child2orient[j] = matingorient[rank[i]][j];
				}

				// Simulated single point crossover of remaining part for first child
				site = k;
				j=0;
				while (k < n)
				{
					flag = false;
					for (temp=0;temp<k;temp++)
					{
						if (child1[temp] == mating[rank[i]][(site+j)%n])
						{
							flag = true;
							break;
						}
					}
					if (flag == false)
					{
						child1[k] = mating[rank[i]][(site+j)%n];
						child1orient[k] = matingorient[rank[i]][(site+j)%n];
						k++;
					}
					j++;
				}

				// Simulated single point crossover of remaining part for second child
				k=site;
				j=0;
				while (k < n)
				{
					flag = false;
					for (temp=0;temp<k;temp++)
					{
						if (child2[temp] == mating[i][(site+j)%n])
						{
							flag = true;
							break;
						}
					}
					if (flag == false)
					{
						child2[k] = mating[i][(site+j)%n];
						child2orient[k] = matingorient[i][(site+j)%n];
						k++;
					}
					j++;
				}
			}

			rank[rank[i]] = -1;
			rank[i] = -1;
		}

		// Mutation
		for (i=0;i<popsize;i++)
		{
			for (j=0;j<n;j++)
			{
				// Swap mutation
				if (genrand() < pmswap)
				{
					k = (int)(genrand()*(n-1));

					temp = mating[i][j];
					mating[i][j] = mating[i][k];
					mating[i][k] = temp;
				}

				// Rotate mutation
				if (genrand() < pmrotate)
				{
					matingorient[i][j] = (matingorient[i][j]+1)%2;
				}
			}
		}

		// copy solutions to population
		for (i=0;i<popsize;i++)
		{
			for (j=0;j<n;j++)
			{
				pop[i][j] = mating[i][j];
				//cout << pop[i][j];
				orient[i][j] = matingorient[i][j];
			}
			//cout << endl;
		}
	}

	fc((int)pos,true);
	cout << "</space>";

	return 0;
}
